\section{Première étape: coloration des instructions atomiques}
\label{distrib-first-step}

\subsection{L'intuition de la première étape}
La distribution commence par une étape de pré-coloration directe, c'est-à-dire que toutes les variables qui se trouvent dans la table de localisation seront colorées dans une couleur choisie pour le site auquel elles sont assignées (une couleur différente par site). Ensuite, il va évidemment falloir respecter la propriété d'atomicité de certains blocs d'instructions. Pour ce faire, voyons tout d'abord comment représenter un bloc atomique en graphe. \\

Le principe d'atomicité d'un bloc signifie que celui-ci s'exécute sur un même site. Il va donc falloir colorer les différents n\oe{}uds, représentant les instructions de ce bloc, de la même couleur. Or nous savons que les n\oe{}uds connectés entre eux doivent être de la même couleur. Il est donc facile de se rendre compte que la meilleure solution de représentation d'un bloc atomique est de connecter tous les n\oe{}uds de ce bloc entre eux, et d'ainsi former ce qu'on appelle un composant connecté (la définition est donnée, pour rappel, ci-dessous). Dès lors, chaque composant connecté du graphe associé au code de l'application de contrôle aura une seule couleur. \\

\begin{definition}{Composant connecté}
	Un composant connecté d'un graphe non dirigé est un sous-graphe de celui-ci tel que pour chaque paire de n\oe{}uds $(a, b)$ du sous-graphe, il existe un chemin allant de $a$ à $b$.
\end{definition} 

\bigskip
Illustrons ceci par un exemple en prenant un \texttt{WHEN} comme bloc atomique. Le code de cet exemple est montré en figure~\ref{fig-distrib-first-code-ex-01} et le graphe associé est représenté en figure~\ref{fig-distrib-first-graph-ex-01}. Ce graphe illustre également la notion de composant connecté introduite ci-dessus. \\

\begin{figure}[!h]
	{\small
	\begin{alltt}
	01:   WHEN a == 3 THEN
	02:       b := TRUE;
	03:   END_WHEN
	\end{alltt}
	}
	\caption{Le code d'un \texttt{WHEN} en \textsl{dSL}}
	\label{fig-distrib-first-code-ex-01}
\end{figure} 

\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.7]{Images/image_3_2.pdf}
		\caption{Le graphe associé à un \texttt{WHEN} est un composant connecté}
		\label{fig-distrib-first-graph-ex-01}
	\end{center}
\end{figure}

\subsection{La formalisation de la première étape}
Après cette intuition sur la façon de distribuer les instructions atomiques, voyons les définitions formelles de celle-ci. Tout d'abord, définissons \textit{table de localisation}, \textit{Coloration compatible}, \textit{flot de contrôle synchrone}, \textit{Graphe de la coloration atomique} et, enfin, \textit{Problème de la coloration atomique}. Toutes ces définitions sont reprises de~\cite{BDeW} et sont traduites pour ce travail. \\

\begin{definition}{Table de localisation}
	Une table de localisation $T$ pour un programme dSL $P$ est une assignation totale des variables externes à l'ensemble des sites: $T \in Var^{in}(P) \cup Var^{out}(P) \mapsto S$, où $S$ est l'ensemble des sites.
\end{definition}

\bigskip

\begin{definition}{Coloration compatible}
	Une coloration $c$ est un \textsl{mapping} de l'ensemble des instructions et des variables vers l'ensemble des sites. Une coloration $c$ est compatible avec une table de localisation $T$ si
	\begin{align*} 
		\forall x \in Var^{in}(P) \cup Var^{out}(P): c(x) = T(x)
	\end{align*}
\end{definition}

\bigskip

\begin{definition}{Flot de contrôle synchrone}
	Une instruction $i'$ peut être atteinte à travers un flot de contrôle synchrone depuis $i$, noté $i \leadsto_a i'$ si une des conditions suivantes est vraie : \\
	
	\begin{itemize}
		\item $i$ et $i'$ sont consécutives dans le même \texttt{WHEN} ;
		\item $i'$ est la condition d'un \texttt{WHEN} qui pourrait être activée directement par l'exécution de $i$, c'est-à-dire que $i$ affecte une variable qui apparaît ou peut être référencée dans la condition $i'$ ;
		\item $i'$ est la première instruction d'une méthode appelée par $i$ sans \texttt{LAUNCH}
	\end{itemize}
\end{definition}

\bigskip
Maintenant, tous les outils ont été donnés pour définir le graphe qui nous servira à résoudre le problème de la coloration atomique. Voyons la définition formelle de ce graphe et la définition du problème. \\

\begin{definition}{Graphe de la coloration atomique}
	Le graphe de la coloration atomique $G_a$ est un graphe $G_a(V, E, T)$ associé à un programme dSL $P$ et une table de localisation $T$, où $V = \lbrace i \; | \; \text{i est une instruction de P} \cup Var(P) \rbrace$ est l'ensemble des n\oe{}uds, et $E = \lbrace \lbrace v, v' \rbrace \; | \; v, v' \in V \rbrace$ est l'ensemble des arcs qui sont caractérisés comme suit : \\
	
	\begin{itemize}
		\item $\forall x \in Var(P), \forall i \in instr(P) : x \in used(i) \Rightarrow \lbrace x, i \rbrace \in E$
		\item $\forall i, i' \in instr(P): i \leadsto_a i' \Rightarrow \lbrace i, i' \rbrace \in E$
	\end{itemize}
\end{definition}

\bigskip
La notion de $used(i)$ est assez facile à comprendre, il s'agit de l'ensemble des variables utilisées dans $i$ et des variables qui peuvent être référencées avec l'utilisation, dans $i$, d'une structure un peu particulière, comme les tableaux, par exemple. Nous pouvons, enfin, définir le problème de la coloration atomique. \\

\begin{definition}{Problème de la coloration atomique}
	Le problème de la coloration atomique consiste, étant donné un graphe de coloration atomique $G_a$, à trouver une fonction $c : V \mapsto S$ compatible avec $T$ telle que pour tout composant connecté $C$ dans $G_a$ :
	\begin{align*}
		n, n' \in C \Rightarrow c(n) = c(n')
	\end{align*}
\end{definition}

\bigskip
Ceci impose bien que les blocs atomiques doivent être colorés de la même manière puisque ceux-ci forment un composant connecté (comme nous avons pu le voir sur un exemple au début de cette section). \\

Après cette coloration, parmi l'ensemble des instructions atomiques, il ne restera que celles qui sont liées à des variables qui ne se trouvent pas dans la table de localisation, c'est-à-dire qu'aucune contrainte n'a été imposée sur celle-ci. Ces instructions peuvent être distribuées sur n'importe quel site. Mais on pourrait imaginer que certains sites conviennent mieux que d'autres par rapport, par exemple, à la charge de travail de chaque site. En effet, on voudrait peut-être équilibrer cette charge de travail et donc distribuer ces blocs atomiques sur des sites avec le minimum de charge de travail. \\

Maintenant, il ne reste que les instructions séquentielles à distribuer, ce qui sera expliqué et défini dans la prochaine section.